package DataStructure_ZL.搜索树哈希和mapset.mapset力扣题;

import java.util.*;

public class mapSet {
    /*
    给定一个非空整数数组，除了某个元素只出现一次以外，
    其余每个元素均出现两次。找出那个只出现了一次的元素。
     */
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> temp = new HashMap<>();
        for (int num : nums) {
            if (temp.get(num) == null) {
                temp.put(num, 1);
            } else {
                temp.remove(num);
            }
        }
        for (int num : nums) {
            if (temp.containsKey(num)) {
                return num;
            }
        }
        return -1;
    }

    /*
    给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针
     random ，该指针可以指向链表中的任何节点或空节点。
     https://leetcode.cn/problems/copy-list-with-random-pointer/
     */
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copyRandomList(Node head) {
        //将原本节点的地址值和新的地址值组成一个map集合，
        //再通过键值对应找新的next值
        if (head == null) return head;
        Map<Node, Node> temp = new HashMap<>();
        Node cur = head;
        while (cur != null) {
            temp.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            temp.get(cur).next = temp.get(cur.next);
            temp.get(cur).random = temp.get(cur.random);
            cur = cur.next;
        }
        return temp.get(head);
    }

    /*
    给你一个字符串 jewels代表石头中宝石的类型，另有一个字符串
    stones 代表你拥有的石头。stones中每个字符代表了一种你拥有
    的石头的类型，你想知道你拥有的石头中有多少是宝石。
    https://leetcode.cn/problems/jewels-and-stones
     */
    public int numJewelsInStones(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < jewels.length(); i++) {
            set.add(jewels.charAt(i));
        }
        int count = 0;
        for (int i = 0; i < stones.length(); i++) {
            if (set.contains(stones.charAt(i))) count++;
        }
        return count;
    }

    /*
    给定一个单词列表words和一个整数 k ，返回前k个出现次数最多的单词。返回的答案应该
    按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
    https://leetcode.cn/problems/top-k-frequent-words
     */
    public List<String> topKFrequent(String[] words, int k) {
        if (words.length<=0) return null;
        //1、统计单词出现的次数  key:单词   val: 次数
        Map<String, Integer> map = new HashMap<>();
        for (String s : words) {
            if (map.get(s) == null) {
                map.put(s, 1);
            } else {
                map.put(s, map.get(s) + 1);
            }
        }
        //2、建立大小为k的 小根堆
        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0) {
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue().compareTo(o2.getValue());
            }
        });
        //遍历map
        for (Map.Entry<String, Integer> s : map.entrySet()) {
            if (pq.size() < k) {
                pq.offer(s);
            } else {
                //此时需要和堆顶元素去比较
                Map.Entry<String, Integer> top = pq.peek();
                assert top != null;
                Integer val = top.getValue();
                if (val.compareTo(s.getValue()) < 0) {
                    pq.poll();
                    pq.offer(s);
                } else if (val.compareTo(s.getValue()) == 0) {
                    if (top.getKey().compareTo(s.getKey()) > 0) {
                        pq.poll();
                        pq.offer(s);
                    }
                }
            }
        }
        //存入集合
        List<String> iu = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            iu.add(pq.poll().getKey());
        }
        Collections.reverse(iu);
        return iu;
    }

}


